Since the packet arrival time interval in data network is in random, the burst data traffic which has exceeded the processable capacity of a network node may lead to data congestion when passing through the network node.
Currently, to avoid the impact of the burst data traffic on communications, the packet traffic policing method based on token bucket is generally used. FIG. 1 is the schematic diagram of the principle of the packet traffic policing method based on token bucket. As shown in FIG. 1, tokens are injected to the token bucket with a capacity of V bytes at an injection rate of v bytes/s, wherein if the token bucket is full, the injected tokens will be discarded. When a packet arrives, if the packet length is less than the quantity of tokens in the token bucket, the token quantity of the token bucket is deducted by the packet length and the packet is allowed to pass through; otherwise, the packet will be discarded. The above-mentioned v refers to the average traffic allowing the packet to pass through, and the token bucket capacity V refers to the burst traffic allowing the packet to pass through.
In the packet traffic policing method based on token bucket, the constant interval of token injection should be firstly determined when realizing token injection. If the constant interval is larger, dramatic fluctuation may be caused in the packet passing rate, thus failing to achieve the traffic policing effect. If the constant interval is small herein, the system will need to perform adding the tokens frequently, which can consume a lot of operation resources.
Currently, in order to make the constant interval more reasonable in the related art, a method for performing adding token only when the packet arrives is provided. In this method, every time a packet arrives, the token quantity which should be accumulated in the token bucket within the time interval between the arrival time of the current packet and the arrival time of the previous packet will be calculated. Specifically, a timer is set to record the arrival time of a packet each time when the packet arrives. When a packet arrives, the arrival time interval of the present packet will be calculated by using the arrival time of current packet and that of the previous packet. Then, within this period of time, the accumulated token quantity of the token bucket=the arrival time interval of the packet×the injection rate of the token. After the accumulated token quantity is added into the token bucket, the processing for the packet length judgment is performed. When using this method, if the arrival time interval of a packet is too long, the timer will overflow, thus leading to an error in the accumulated token quantity calculation.
In the existing network nodes, the arrival packets shall be classified according to attributes, such as source address, destination address and so on, wherein the packets classified into the same one category are defined as a flow. As to a large-capacity network node, the flow quantity may be tremendous, so it is needed to distinguish various flows and set different token bucket capacities and token injection rates. Based on this situation, a method for traffic policing of token bucket packet which is easily realized by hardware chips is provided in the related art. In this method, the maximum timer depth Tmax needed by the system is firstly calculated. For a system, the time period during which the token bucket with maximum depth is filled up at a minimum token injection rate is the maximum timer depth needed by the system. As to any flow in a system, when the arrival time interval of two packets is larger than this time period, the token bucket has overflowed obviously. At this moment, it is only necessary to fill up directly the corresponding token bucket but without calculating the accumulated token quantity.
Specifically, in this method, a dual-port Random Access Memory (RAM) is used to calculate the packet arrival time interval of each flow, wherein the dual-port RAM records the arrival time of previous packet of each flow and the carry flag of the timer (each time the timer expires, the carry flag bit is reversed) at this arrival time, and at the same time an overflow flag bit is provided for overflow scanning processing. The two access ports of the dual-port RAM are used to record packet arrival time and to perform overflow scanning processing respectively. The above-mentioned overflow scanning processing is to scan for the arrival time of all packets stored in the dual-port RAM in sequence, and the overflow flag bit is set as 0 each time of recording the arrival time of a new packet, while this overflow flag bit is set as 1 if the constant interval is found to have overflowed during the process of scanning. It is needed to scan all the flows for one time within the time Tmax, wherein when scanning, the packet arrival time T1 of the flow to be scanned is read out and is compared with the current timer time T2. If the overflow flag which is read out is 0, T1 and T2, and the carry flag of T1 and the carry flag of T2 are compared, wherein if the carry flags are the same and T2>T1, it indicates that the token bucket has not overflowed from T1 to the current time, and if the two carry flags are the same and T2<T1, it indicates that the timer has implemented for two cycle and the token bucket has overflowed from T1 to the current time, and if the two carry flags are different and T2>T1, it indicates that the timer has implemented for one cycle and the token bucket has overflowed from T1 to the current time, and if the two carry flags are the different and T2<T1, it indicates that the timer has implemented for one cycle and the token bucket has not overflowed from T1 to the current time. If the overflow flag which is read out is 1, it illustrates that the token bucket has overflowed and no operation is performed. Since the scanning interval is Tmax, for any flow the arrival time of the lately updated packet may be all marked as “token bucket overflow” within the time 2Tmax. After a packet arrives, the arrival time interval of the packet is calculated by the same judgment method. In this way, when the packet arrival time interval is less than 2Tmax, whether the token bucket has overflowed can be correctly judged; while for the situation that the packet arrival time interval is larger than 2Tmax, it can be solved by performing the overflow scanning processing.
In this method, a dual-port RAM needs to be used, but over ten thousand different flows shall be identified in the existing network node, and the speed limit rates of these diversified flows may be different million times. Therefore, the width of the timer used for calculating the packet arrival time interval may be up to over 20 bits. As to hardware chips, the available dual-port RAM quantity inside the chips is limited. When the flow density is very high (16,000 flows) and the width of the timer is very wide (over 20 bits), a large storage space is needed, so unfavorable to the realization by means of an internal RAM. Nevertheless, if a external RAM (connected outside) is used, the processing speed of packet may be affected since the scanning processing has certain correlation with packet interval calculation processing (the overflow flag bit needs to be considered) and the operation delay of the external RAM is relatively larger.